A file server provides one or more clients with access to files of a file system in data storage. A popular kind of file system is a UNIX-based file system as described in Uresh Vahalia, Unix Internals—The New Frontiers, Chapter 9, File System Implementations, pp. 261-290, Prentice-Hall, Inc., Upper Saddle River, N.J. (1996). A file in a Unix-based file system is a hierarchy of file system blocks. The file system block at the top or root of the hierarchy is called an “inode.” The inode contains attributes of the file, such as the file type, the size of the file, user and group IDs of the owner of the file, timestamps, and permissions and mode flags. The inode also contains a block pointer array including pointers to one or more file system blocks that are directly below the inode in the hierarchy. The data of the file is contained in one or more file system blocks at the bottom or leaves of the hierarchy. If the file contains more than ten data blocks, then there will be at least one indirect block directly below inode in the hierarchy.
The fact that the file contains pointers to the data blocks in the file permits any free block of the file system to be allocated to a file of the file system and mapped to any logical block of the logical extent of the file. The additional flexibility of file system block allocation permits more efficient storage utilization by reducing storage fragmentation and permitting sparse files and efficient dynamic extension of files.
When files are created or extended, or holes are filled in sparse files, there is a need to locate blocks of free storage available for allocation to the file. Typically this storage resource location process involves searching for free physical storage blocks that have already been allocated to the file system. For example, physical storage typically is allocated to the file system in multiples of a unit called a “cylinder group.” Each cylinder group includes a cylinder group header followed by multiple file system blocks. For example, the file system block size is 8 kilobytes, the cylinder group size is 64 megabytes, and the cylinder group header occupies one 8 kilobyte block.
The cylinder group header includes a data structure describing summary information about that cylinder group. This summary information includes a free inode list and a free block list. When a new file is created, the free inode list is searched to find a free inode to be allocated to the new file. When an indirect block or a data block is needed for a new file or for extending an existing file, then the free block list is searched to find a free block to be allocated to the file.
Recently there has been a need to decrease the burden and cost of storage management and administration. The number and size of file systems to be managed have been increasing due to a continuing increase in processing power and decrease in storage cost. Thin provisioning by the use of virtual storage is an increasingly popular way of dealing with the increase in the number and size of file systems. Virtual storage provides a way of dynamically provisioning a file system with physical storage as a file system grows. A file system can be built upon a very large sparse metavolume provisioned with a small amount of physical storage. In this case, the blocks of virtual storage in the sparse metavolume include some blocks that are provisioned with physical storage, and other blocks that are not provisioned with physical storage. By building a file system upon a sparse metavolume, the system administrator is relieved of the burden of frequently reconfiguring the file system as the number of allocated blocks in the file system reaches the size of the logical volume upon which the file system is built.